1. Field of the Invention
The present invention relates to signal processing, and, in particular, to error correction encoding and decoding techniques such as low-density parity-check (LDPC) encoding and decoding.
2. Description of the Related Art
FIG. 1 shows one implementation of a parity-check matrix 100 that may be used to implement a regular, quasi-cyclic (QC) LDPC code. Parity-check matrix 100, commonly referred to as an H-matrix, comprises 40 circulants Bj,k that are arranged in r=4 rows of circulants where j=1, . . . , r and c=10 columns of circulants where k=1, . . . , c. Each circulant Bj,k is a p×p sub-matrix that may be obtained by circularly shifting a single p×p identity matrix. For purposes of this discussion, assume that p=72 such that H-matrix 100 has p×r=72×4=288 total rows and p×c=72×10=720 total columns. Since each circulant Bj,k is a permutation of an identity matrix, the hamming weight (i.e., the number of entries having a value of one) of each column in a circulant and the hamming weight of each row in a circulant are both equal to 1. Thus, the total hamming weight wr for each row of H-matrix 100 is equal to 1×c=1×10=10, and the total hamming weight wc for each column of H-matrix 100 is equal to 1×r=1×4=4. Each of the 288 rows of H-matrix 100 corresponds to a different check node cm, where m ranges from 1, . . . , 288, and each of the 720 columns corresponds to a different variable node bn (also referred to as a bit node), where n ranges from 1, . . . , 720. Further, each check node cm is connected to wr=10 bit nodes as indicated by the Is in a row, and each variable node bn is connected to wc=4 check nodes as indicated by the 1s in a column. H-matrix 100 may be described as a regular LDPC code since all rows of H-matrix 100 have the same hamming weight wr and all columns of H-matrix 100 have the same hamming weight wc.
FIG. 2 shows a simplified block diagram of one implementation of a prior-art LDPC decoder 200 that may be used to decode a signal encoded using an H-matrix such as H-matrix 100 of FIG. 1. LDPC decoder 200 receives 720 soft values (e.g., log-likelihood ratios) from a soft detector such as a soft-output Viterbi detector and stores these soft values in soft-value memory 202. Each soft value corresponds to one bit of a received LDPC-encoded codeword. The encoded codeword is decoded iteratively using a belief propagation technique, where each iteration is performed in a number of clock cycles that is equal to the number c of circulant columns (e.g., 10 clock cycles/iteration for H-matrix 100).
During the first clock cycle of the initial iteration, soft-value memory 202 provides the first 72 of 720 soft values in parallel to 72 variable node units (VNUs) 204(0), . . . ,(71), such that each soft value is provided to a different VNU 204. VNUs 204(0), . . . ,(71) perform variable node updates for the first 72 columns of H-matrix 100 (i.e., for the first circulant column comprising circulants B1,1, B2,1, B3,1, and B4,1). Specifically, each VNU 204 generates one variable node message for each of the four circulants B1,1, B2,1, B3,1, and B4,1 (e.g., one message for each column entry having a value of 1 implies four messages per column), such that the total number of variable node messages generated by VNUs 204(0), . . . ,(71) is equal to 4×72=288. During the initial iteration (i.e., i=0), each variable node message may be generated per Equation (1) as follows:Qnm(0)=Ln(0), where   (1)Qnm(0) is the variable node message provided from the nth variable node bn to the mth check node cm for the 0th iteration and Ln(0) is the initial soft value received from soft-value memory 202 that corresponds to the nth variable node.
VNUs 204(0), . . . ,(71) provide the 4×72 variable node messages (herein referred to as Q messages) that they generate to four 72-way barrel shifters 206(0), . . . ,(3). In particular, the 72 Q messages generated in relation to circulant B1,1, the 72 Q messages generated in relation to circulant B2,1, the 72 Q messages generated in relation to circulant B3,1, and the 72 Q messages generated in relation to circulant B4,1 are provided to separate barrel shifters 206(0), . . . ,(3), respectively. Barrel shifters 206(0), . . . ,(3) cyclically shift the Q messages that they receive based on cyclic-shift factors that (i) correspond to the cyclic shifts of circulants B1,1, B2,1, B3,1, and B4,1 of H-matrix 100 of FIG. 1 and (ii) may be received from, for example, controller 214. The four barrel shifters 206 then provide 4×72 cyclically shifted Q messages to 4×72 check node units (CNUs) 208(0), . . . ,(287), such that each CNU 208 receives a different one of the Q messages.
Note that barrel shifters 206(0), . . . ,206(3) are used to distribute Q messages from VNUs 204(0), . . . ,(71) to the proper CNUs 208. Rather than using barrel shifters 206, fixed connections could be made between VNUs 204(0), . . . ,(71) and CNUs 208(0), . . . ,(287) to distribute the Q messages. However, such fixed connections support only a limited number of different H-matrices. The use of 72-way barrel shifters, on the other hand, allows LDPC decoder 200 to support up to 72 different circulant variations. Each of the of the 40 circulants Bj,k in FIG. 100 may take the form of any one of the 72 different circulant variations and the 72 different circulant variations may be combined in any of a number of different manners to generate a number of different H-matrices.
FIG. 3 shows a simplified block diagram of one implementation of a prior-art 72-way barrel shifter 300 that may be used to implement barrel shifters 206(0), . . . ,(3) of FIG. 2. Barrel shifter 300 has seven stages (i.e., stages 0, . . . ,6), each of which is capable of providing two different shift factors based on a shift signal (e.g., shift[0], . . . , shift[6]) received from, for example, controller 214 of FIG. 2. Stage 0 is capable of shifting by a factor of 0 or 1, stage 1 is capable of shifting by a factor of 0 or 2, stage 2 is capable of shifting by a factor of 0 or 4, and so on. Each stage comprises 72 multiplexers, which perform cyclic shifting based on the shift signal.
As an example of a shift operation, suppose that the desired shift factor is 3. This shift factor may be obtained by asserting (i.e., setting equal to 1) shift[0] and shift[1] and deasserting (i.e., setting equal to 0) shift[2] to shift[6]. Multiplexers 302(0), . . . , 302(71) of stage 0 have upper inputs, which receive input values inp[0], . . . ,inp[71], respectively, and lower inputs that receive input values inp[1], . ,inp[71], inp[0], respectively. By asserting shift[0], input values inp[1], . . . ,inp[71], and inp[0] (i.e., the lower inputs of stage 0) are output from multiplexers 302(0), . . . , 302(71), respectively, such that the input values are shifted by 1.
The upper inputs of multiplexers 304(0), . . . , 304(71) of stage 1 receive stage 0 output values stg0[0], . . . , stg0[71] (i.e., inp[1], . . . ,inp[71], and inp[0]), respectively, and the lower inputs of multiplexers 304(0), . . . , 304(71) receive stage 0 output values stg0[2], . . . , stg0[71], stg0[0], stg0[1] (i.e., inp[3], . . . ,inp[71], and inp[0], . . . ,inp[2]), respectively. By asserting shift[1], stage 0 output values stg0[2], . . . , stg0[71], stg0[0], stg0[1] (i.e., the lower inputs of stage 1), respectively, are output from multiplexers 304(0), . . . , 304(71), such that the stage 0 output values are shifted by 2. The stage 1 output values are then sequentially processed by stages 2, . . . , 6, each of which provides a shift factor of 0. The final shift factor of 3 is determined by summing the shift factors for stages 0, . . . , 6.
Referring back to FIG. 2, during the second clock cycle of the first iteration, VNUs 204(0), . . . ,(72) receive the second 72 of 720 soft values from soft-value memory 202. VNUs 204(0), . . . ,(72) perform variable node updates for the second 72 columns of H-matrix 100 (i.e., for the second circulant column comprising circulants B1,2, B2,2, B3,2, and B4,2) in a manner similar to that described above in relation to the first clock cycle (e.g., using Equation (1)) and provide 4×72 Q messages to barrel shifters 206(0), . . . ,(3). Barrel shifters 206(0), . . . ,(3) cyclically shift the 4×72 Q messages according to the cyclic shifts of circulants B1,2, B2,2, B3,2, and B4,2 of H-matrix 100 of FIG. 1 and provide 4×72 cyclically shifted Q messages to check node units (CNUs) 208(0), . . . ,208(287). Note that, cyclic shifting of the 4×72 Q messages is performed such that each Q message is distributed to the same CNU as the Q message from the prior clock cycle that corresponds to the same row (i.e., the same check node cm) of H-matrix 100. This process is repeated for the remaining 8 circulant columns during the remaining 8 clock cycles of the iteration.
Referring now to CNUs 208(0), . . . , (287), during the first iteration (i.e., the first 10 clock cycles), each of the CNUs receives a number of Q messages equal to the hamming weight wr of a row of H-matrix 100 (e.g., 10) and generates wr check node messages. Each check node message may be calculated using a min-sum algorithm, characterized by Equations (2), (3), and (4) shown below:
                              R          mn                      (            i            )                          =                              δ            mn                          (              i              )                                ⁢                      κ            mn                          (              i              )                                                          (        2        )                                          κ          mn                      (            i            )                          =                                                        R              mn                              (                i                )                                                          =                                    min                                                n                  ′                                ∈                                                      N                    ⁡                                          (                      m                      )                                                        /                  n                                                      ⁢                                                        Q                                                      n                    ′                                    ⁢                  m                                                  (                                      i                    -                    1                                    )                                                                                                      (        3        )                                                      δ            mn                          (              i              )                                =                      (                                          ∏                                                      n                    ′                                    ∈                                                            N                      ⁡                                              (                        m                        )                                                              /                    n                                                              ⁢                                                          ⁢                              sign                ⁡                                  (                                      Q                                                                  n                        ′                                            ⁢                      m                                                              (                                              i                        -                        1                                            )                                                        )                                                      )                          ,                            (        4        )            where Rmn(i) represents the check node message (herein referred to as the R message) from the mth check node cm to the nth variable node bn for the ith iteration. Suppose that a set n′ of variable nodes includes all variable nodes N(m) connected to check node cm except variable node bn (i.e., n′εN(m)/n). Check node cm generates message Rmn(i) based on all Q messages received during the previous (i−1)th iteration from the set of bit nodes N(m) connected to check node cm except the Q message received from bit node bn (i.e., Qnm(i−1)). Thus, in the embodiment of FIG. 2, each R message is generated based on nine Q messages (i.e., wr−1=10−1).
Message Rmn(i) may be calculated in several steps. First, check node cm generates a sign δmn(i) for message Rmn(i) by taking the product of the signs of the Q messages in set n′ as shown in Equation (4). This can also be performed using binary addition, such as a modulo 2 operation, of the signs rather than multiplication. Next, check node cm generates a magnitude |Rmn(i)| for message Rmn(i) by determining the minimum magnitude of the Q messages in set n′ as shown in Equation (3). Then, check node cm multiplies sign δmn(i) by magnitude |Rmn(i)| as shown in Equation (2). Note that, other variations of the min-sum algorithm are possible such as an offset min-sum algorithm and a normalized min-sum algorithm. Further, CNU algorithms other than the min-sum algorithm, such as the sum product algorithm, may be used.
The min-sum algorithm described in Equations (2), (3), and (4) may be simplified using a value-reuse technique. For example, consider that, during an iteration, each CNU 208 receives ten Q messages and generates ten R messages. Each R message is generated using a set of n′=9 Q messages (one message is excluded as described above). For nine of these R messages, the minimum magnitude of the Q messages generated using Equation (3) will be the same. For one of these R messages, the minimum magnitude of the Q messages will be the second smallest magnitude of the Q messages because the minimum magnitude of the Q messages will be excluded from the calculation as described above. Thus, it is not necessary to perform Equation (3) 10 times for each CNU. Rather, each CNU may receive its corresponding ten Q messages during an iteration, store the two Q messages with the smallest magnitude, and store an index value corresponding to the minimum magnitude. The index value may be used to match the second smallest magnitude with the correct R message.
Referring back to FIG. 2, the min-sum algorithm performed by CNUs 208(0), . . . , (287) may be a two-step process performed over two iterations. For example, during the ith iteration (i.e., 10 clock cycles), each CNU 208 receives and processes ten Q messages. These messages may be processed by (1) determining the minimum and second minimum values, (2) summing the signs of the ten Q messages, and (3) providing the signs of the ten Q messages sequentially to FIFO 210. Each CNU 208 does not begin outputting the ten R messages it generates until the (i+1)th iteration (i.e., after it has received all ten Q messages). During the (i+1)th iteration, each CNU 208 may receive ten new Q messages at a rate of one per clock cycle and may output the ten R messages at a rate of one per clock cycle. Upon being output, each R message is multiplied by a different sign value δmn(i) that may be obtained by adding (i) the sum of the signs of the ten Q messages and (ii) a sign received from FIFO 210 that corresponds to message Qnm(i−1). In so doing, one sign of the Q messages is excluded from sign value δmn(i) as shown in Equation (4) (i.e., sign δmn(i) is generated based on the signs of nine Q messages rather than ten).
During each clock cycle, each barrel shifter 212 receives 72 R messages in parallel and cyclically shifts the R messages according to the cyclic shifts of the circulants Bj,k of H-matrix 100 of FIG. 1, which may be provided by controller 214. Essentially, barrel shifters 212(0), . . . ,(3) reverse the cyclic shifting of barrel shifters 206(0), . . . ,(3). Barrel shifters 212(0), . . . ,(3) then provide the 4×72 cyclically shifted R messages to VNUs 204(0), . . . ,(71), such that each VNU 204 receives four of the R messages.
During the second iteration, each VNU 204 updates each of the four Q messages that it generates as shown in Equation (5):
                                          Q                          n              ⁢                                                          ⁢              m                                      (              i              )                                =                                    L              n                              (                0                )                                      +                                          ∑                                                      m                    ′                                    ∈                                                            M                      ⁡                                              (                        n                        )                                                              /                    m                                                              ⁢                              R                                                      m                    ′                                    ⁢                  n                                                  (                                      i                    -                    1                                    )                                                                    ,                            (        5        )            where m′ is a set of check nodes that includes all check nodes M(n) connected to variable node bn except check node cm (i.e., m′εM (n)/m). Variable node bn generates message Qnm(i) based on (i) all R messages received during the previous (i−1)th iteration from the set of all check nodes M(n) connected to variable node bn except the R message received from check node cm (i.e., Rmn(i−1)) and (ii) the initial soft value Ln(0) received from soft value memory 202 that corresponds to the nth variable node.
In addition to outputting four updated Q messages, each VNU 204 outputs both (i) a soft value (i.e., an extrinsic LLR) and (ii) a hard-decision bit for each bit node bn. Each extrinsic LLR value may be represented as shown in Equation (6):
                                          Extrinsic            ⁢                                                  ⁢                          Value              n                                =                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                          R              mn                              (                i                )                                                    ,                            (        6        )            where the set of m check nodes includes the set M(n) of all check nodes cm connected to variable node bn (i.e., mεM(n)). Each hard-decision bit {circumflex over (x)}n may be generated based on Equations (7), (8), and (9) below:
                              P          n                =                              L            n                          (              0              )                                +                                    ∑                              m                ∈                                  M                  ⁡                                      (                    n                    )                                                                        ⁢                          R              mn                              (                i                )                                                                        (        7        )                                                      x            ^                    n                =                              0            ⁢                                                  ⁢            if            ⁢                                                  ⁢                          P              n                                ≥          0                                    (        8        )                                                      x            ^                    n                =                              1            ⁢                                                  ⁢            if            ⁢                                                  ⁢                          P              n                                <          0                                    (        9        )            Pn is determined for each variable node bn by adding the extrinsic value from Equation (6) to the initial soft value Ln(0) received from soft-value memory 202 that corresponds to the nth variable node. If Pn is greater than or equal to zero, then the hard decision bit {circumflex over (x)}n is set equal to zero as shown in Equation (8). If Pn is less than zero, then the hard decision bit {circumflex over (x)}n is set equal to one as shown in Equation (9).
A parity check is then performed using the hard-decision values. If {circumflex over (x)}HT=0, where HT is the transpose of H-matrix 100 of FIG. 1, then the decoding process is finished. If {circumflex over (x)}HT≠0, then a subsequent iteration is performed to generate a new set of extrinsic LLR values and hard decisions. If the decoding process does not end within a predefined number of iterations, then the decoding process is terminated and the received codeword has not been properly decoded.